package com.cn.algorithm.leetcode.array.two;


/*
*
* 找出字符串中第一个匹配项的下标
简单
相关标签
相关企业
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。



示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。


提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
*
*
* */
public class FirstSubscript {

    public static void main(String[] args) {
        String haystack = "mississippi", needle = "issip";
        //System.out.println(haystack.substring(0, needle.length()));
        System.out.println(strStr(haystack, needle));
    }

    public static int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length(); i++) {
            if ((needle.length() + i) <= haystack.length() &&
                    haystack.charAt(i) == needle.charAt(0) &&
                    haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
        return -1;
    }


    /*
    * 官方解法：
    * 方法二：Knuth-Morris-Pratt算法
思路及算法

Knuth-Morris-Pratt算法，简称 KMP 算法，由 Donald Knuth、James.H.Morris 和 Vaughan Pratt三人于 197719771977 年联合发表。

Knuth-Morris-Pratt算法的核心为前缀函数，记作 π(i)，其定义如下：

对于长度为 m的字符串 s，其前缀函数 π(i)(0≤i<m) 表示 sss 的子串 s[0:i] 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 π(i)=0。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

我们举个例子说明：字符串 aabaaab 的前缀函数值依次为 0,1,0,1,2,2,3。

π(0)=0，因为 a 没有真前缀和真后缀，根据规定为 0（可以发现对于任意字符串 π(0)=0）；

π(1)=1，因为 aa 最长的一对相等的真前后缀为 aa，长度为 1；

π(2)=0，因为 aab 没有对应真前缀和真后缀，根据规定为 0；

π(3)=1，因为 aaba 最长的一对相等的真前后缀为 a，长度为 1；

π(4)=2，因为 aabaa 最长的一对相等的真前后缀为 aa，长度为 2；

π(5)=2，因为 aabaaa 最长的一对相等的真前后缀为 aa，长度为 2；

π(6)=3，因为 aabaaab 最长的一对相等的真前后缀为 aab，长度为 3。

有了前缀函数，我们就可以快速地计算出模式串在主串中的每一次出现。

如何求解前缀函数

长度为 m 的字符串 s 的所有前缀函数的求解算法的总时间复杂度是严格 O(m) 的，且该求解算法是增量算法，即我们可以一边读入字符串，一边求解当前读入位的前缀函数。

为了叙述方便，我们接下来将说明几个前缀函数的性质：  以下看官方说法：

    *
    * */
    public int strStr2(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}
